// Written by Craig'n'Dave
using System;
using System.Collections.Generic;
// Binary tree using an array
namespace ConsoleApp1
{
    class Program
    {
        public class Binary_tree
        {
            public class Node
            {
                public string data;
                public Node left_pointer;
                public Node right_pointer;
            }

            public Node root;

            public bool add(string item)
            {
                // Check memiry overflow
                try
                {
                    Node new_node = new Node();
                    new_node.data = item;
                    Node current_node = root;
                    new_node.left_pointer = null;
                    new_node.right_pointer = null;
                    // Tree is empty
                    if (current_node == null)
                    {
                        root = new_node;
                    }
                    else
                    {
                        // Find correct position in the tree
                        Node previous = null;
                        while (current_node != null)
                        {
                            previous = current_node;
                            if (String.Compare(item, current_node.data) < 0)
                            {
                                current_node = current_node.left_pointer;
                            }
                            else
                            {
                                current_node = current_node.right_pointer;
                            }
                        }
                        if (String.Compare(item, previous.data) < 0)
                        {
                            previous.left_pointer = new_node;
                        }
                        else
                        {
                            previous.right_pointer = new_node;
                        }
                    }
                    return true;
                }
                catch
                {
                    return false;
                }
            }
            
            public void delete(string item)
            {
                // Using Hibbard's algorithm (leftmost node of right sub-tree is the successor)
                // Find the node
                Node current_node = root;
                Node previous = null;
                while ((current_node != null) && (current_node .data != item))
                {
                    previous = current_node;
                    if (String.Compare(item, current_node.data) < 0)
                    {
                        current_node = current_node.left_pointer;
                    }
                    else
                    {
                        current_node = current_node.right_pointer;
                    }
                }

                // Handle 3 cases depending on the number of child nodes
                if (current_node != null)
                {
                    if ((current_node.left_pointer == null) && (current_node.right_pointer == null))
                    {
                        // Node has no children
                        if (String.Compare(previous.data, current_node.data) > 0)
                        {
                            previous.left_pointer = null;
                        }
                        else
                        {
                            previous.right_pointer = null;
                        }
                    }
                    else if (current_node.right_pointer == null)
                    {
                        // Node has one left child
                        if (String.Compare(previous.data, current_node.data) > 0)
                        {
                            previous.left_pointer = current_node.left_pointer;
                        }
                        else
                        {
                            previous.right_pointer = current_node.left_pointer;
                        }
                    }
                    else if (current_node.left_pointer == null)
                    {
                        // Node has one right child
                        if (String.Compare(previous.data, current_node.data) > 0)
                        {
                            previous.left_pointer = current_node.right_pointer;
                        }
                        else
                        {
                            previous.right_pointer = current_node.right_pointer;
                        }
                    }
                    else
                    {
                        // Node has two children
                        Node right_node = current_node.right_pointer;
                        if (right_node.left_pointer != null)
                        {
                            // Find the smallest value in the right sub-tree
                            Node smallest = current_node.right_pointer;
                            while (smallest.left_pointer != null)
                            {
                                previous = smallest;
                                smallest = smallest.left_pointer;
                            }
                            // Change the deleted node value to the smallest value
                            current_node.data = smallest.data;
                            // Remove the successor node
                            previous.left_pointer = null;
                        }
                        else
                        {
                            // Handle special case of no left sub-tree from right node
                            current_node.data = right_node.data;
                            current_node.right_pointer = null;
                        }
                    }
                }
            }

            public void preorder(Node current_node)
            {
                if (current_node != null)
                {
                    // Visit each node: NLR
                    Console.WriteLine(current_node.data);
                    if (current_node .left_pointer != null)
                    {
                        preorder(current_node.left_pointer);
                    }
                    if (current_node .right_pointer != null)
                    {
                        preorder(current_node.right_pointer);
                    }
                }
            }

            public void inorder(Node current_node)
            {
                if (current_node != null)
                {
                    // Visit each node: LNR
                    if (current_node.left_pointer != null)
                    {
                        inorder(current_node.left_pointer);
                    }
                    Console.WriteLine(current_node.data);
                    if (current_node.right_pointer != null)
                    {
                        inorder(current_node.right_pointer);
                    }
                }
            }

            public void postorder(Node current_node)
            {
                if (current_node != null)
                {
                    // Visit each node: LRN
                    if (current_node.left_pointer != null)
                    {
                        postorder(current_node.left_pointer);
                    }
                    if (current_node.right_pointer != null)
                    {
                        postorder(current_node.right_pointer);
                    }
                    Console.WriteLine(current_node.data);
                }
            }

            public void bft(Node current_node)
            {
                Queue<Node> q = new Queue<Node>();
                while (current_node != null)
                {
                    Console.WriteLine(current_node.data);
                    if (current_node.left_pointer != null)
                    {
                        q.Enqueue(current_node.left_pointer);
                    }
                    if (current_node.right_pointer != null)
                    {
                        q.Enqueue(current_node.right_pointer);
                    }
                    if (q.Count > 0) { current_node = q.Dequeue(); } else { current_node = null; }                    
                }
            }

        }


        // Main program starts here
        static void Main(string[] args)
        {
            string[] items = { "E", "B", "G", "A", "C", "F", "H" };
            Binary_tree binary_tree = new Binary_tree();
            for (int index = 0; index < items.Length; index++)
            {
                binary_tree.add(items[index]);
            }
            // Traverse the binary tree
            Console.WriteLine("Breadth first traversal:");
            binary_tree.bft(binary_tree.root);
            Console.WriteLine("Pre-order traversal:");
            binary_tree.preorder(binary_tree.root);
            Console.WriteLine("In-order traversal:");
            binary_tree.inorder(binary_tree.root);
            Console.WriteLine("Post-order traversal:");
            binary_tree.postorder(binary_tree.root);
        }
    }
}
